{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kill Process"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: killProcess"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #杀掉进程"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>系统中存在 <code>n</code>&nbsp;个进程，形成一个有根树结构。给你两个整数数组&nbsp;<code>pid</code> 和 <code>ppid</code> ，其中 <code>pid[i]</code> 是第 <code>i</code> 个进程的 ID ，<code>ppid[i]</code> 是第 <code>i</code> 个进程的父进程 ID 。</p>\n",
    "\n",
    "<p>每一个进程只有 <strong>一个父进程</strong> ，但是可能会有 <strong>一个或者多个子进程</strong> 。只有一个进程的 <code>ppid[i] = 0</code> ，意味着这个进程 <strong>没有父进程</strong> 。</p>\n",
    "\n",
    "<p>当一个进程 <strong>被杀掉</strong> 的时候，它所有的子进程和后代进程都要被杀掉。</p>\n",
    "\n",
    "<p>给你一个整数 <code>kill</code> 表示要杀掉​​进程的 ID ，返回被杀掉的进程的 ID 列表。可以按 <strong>任意顺序</strong> 返回答案。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/24/ptree.jpg\" style=\"width: 207px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>pid = [1,3,10,5], ppid = [3,0,5,3], kill = 5\n",
    "<strong>输出：</strong>[5,10]\n",
    "<strong>解释：</strong>涂为红色的进程是应该被杀掉的进程。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>pid = [1], ppid = [0], kill = 1\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == pid.length</code></li>\n",
    "\t<li><code>n == ppid.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= pid[i] &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= ppid[i] &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li>仅有一个进程没有父进程</li>\n",
    "\t<li><code>pid</code> 中的所有值 <strong>互不相同</strong></li>\n",
    "\t<li>题目数据保证 <code>kill</code> 在 <code>pid</code> 中</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kill-process](https://leetcode.cn/problems/kill-process/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kill-process](https://leetcode.cn/problems/kill-process/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,10,5]\\n[3,0,5,3]\\n5', '[1]\\n[0]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        children=dict()\n",
    "        for i in range(len(pid)):\n",
    "            if ppid[i] not in children:\n",
    "                children[ppid[i]] =[]\n",
    "            children[ppid[i]].append(pid[i])  \n",
    "        q = []\n",
    "        q.append(kill) \n",
    "        i=0\n",
    "        while i < len(q)  :\n",
    "            t = q[i]\n",
    "            if(t in children):  \n",
    "                q.extend(  children[t] ) \n",
    "            i+=1\n",
    "        return q\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        children=dict()\n",
    "        for i in range(len(pid)):\n",
    "            if ppid[i] not in children:\n",
    "                children[ppid[i]] =[]\n",
    "            children[ppid[i]].append(pid[i]) \n",
    "        targets= []\n",
    "        import queue\n",
    "        q = []\n",
    "        q.append(kill)\n",
    "        targets.append(kill)\n",
    "        i=0\n",
    "        while i < len(q)  :\n",
    "            t = q[i]\n",
    "            if(t in children): \n",
    "                targets.extend( children[t] ) \n",
    "                q.extend(  children[t] ) \n",
    "            i+=1\n",
    "        return targets\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        children=dict()\n",
    "        for i in range(len(pid)):\n",
    "            if ppid[i] not in children:\n",
    "                children[ppid[i]] =[]\n",
    "            children[ppid[i]].append(pid[i])  \n",
    "        q = []\n",
    "        q.append(kill) \n",
    "        i=0\n",
    "        while i < len(q)  :\n",
    "            t = q[i]\n",
    "            if(t in children):  \n",
    "                q.extend(  children[t] ) \n",
    "            i+=1\n",
    "        return q\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        children=dict()\n",
    "        for i in range(len(pid)):\n",
    "            if ppid[i] not in children:\n",
    "                children[ppid[i]] =[]\n",
    "            children[ppid[i]].append(pid[i]) \n",
    "        targets= []\n",
    "        import queue\n",
    "        q = []\n",
    "        q.append(kill)\n",
    "        targets.append(kill)\n",
    "        i=0\n",
    "        while i < len(q)  :\n",
    "            t = q[i]\n",
    "            if(t in children): \n",
    "                targets.extend( children[t] ) \n",
    "                q.extend(  children[t] ) \n",
    "            i+=1\n",
    "        return targets\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        children=dict()\n",
    "        for i in range(len(pid)):\n",
    "            if ppid[i] not in children:\n",
    "                children[ppid[i]] =[]\n",
    "            children[ppid[i]].append(pid[i]) \n",
    "        targets= []\n",
    "        import queue\n",
    "        q = queue.Queue()\n",
    "        q.put(kill)\n",
    "        targets.append(kill)\n",
    "        while not q.empty()  :\n",
    "            t = q.get() \n",
    "            if(t in children): \n",
    "                targets.extend( children[t] ) \n",
    "                for c in children[t]:\n",
    "                    q.put(c)\n",
    "        return targets\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        children=dict()\n",
    "        for i in range(len(pid)):\n",
    "            if ppid[i] not in children:\n",
    "                children[ppid[i]] =[]\n",
    "            children[ppid[i]].append(pid[i]) \n",
    "        targets= []\n",
    "        import queue\n",
    "        q = queue.Queue()\n",
    "        q.put(kill)\n",
    "        targets.append(kill)\n",
    "        while not q.empty()  :\n",
    "            t = q.get() \n",
    "            if(t in children): \n",
    "                targets.extend( children[t] ) \n",
    "                for c in children[t]:\n",
    "                    q.put(c)\n",
    "        return targets\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        cpid = {}\n",
    "        n = len(pid)\n",
    "        for i in range(n):\n",
    "            if ppid[i] not in cpid:\n",
    "                cpid[ppid[i]] = []\n",
    "            cpid[ppid[i]].append(pid[i])\n",
    "        ans = []\n",
    "        st = [kill]\n",
    "        while len(st) > 0:\n",
    "            c = []\n",
    "            for i in st:\n",
    "                ans.append(i)\n",
    "                if i in cpid:\n",
    "                    c += cpid[i]\n",
    "            st = c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        store = collections.defaultdict(list)\n",
    "        n = len(pid)\n",
    "        for i in range(n):\n",
    "            store[ppid[i]].append(pid[i])\n",
    "        queue, nextQueue = [kill], []\n",
    "        result = []\n",
    "        while queue:\n",
    "            node = queue.pop()\n",
    "            result.append(node)\n",
    "            for child in store.get(node, []):\n",
    "                nextQueue.append(child)\n",
    "            if not queue:\n",
    "                queue = nextQueue[::]\n",
    "                nextQueue = []\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        n = len(ppid)\n",
    "\n",
    "        pid_map = {}\n",
    "        queue = collections.deque()\n",
    "        root = -1\n",
    "        for p, pp in zip(pid, ppid):\n",
    "            if pp == 0:\n",
    "                root = pp\n",
    "            else:\n",
    "                if pp not in pid_map:\n",
    "                    pid_map[pp] = []\n",
    "                pid_map[pp].append(p)\n",
    "        if kill not in pid_map:\n",
    "            return [kill]\n",
    "        else:\n",
    "            killed_process = []\n",
    "            queue.append(kill)\n",
    "            while queue:\n",
    "                killed_process.append(queue.popleft())\n",
    "                if killed_process[-1] in pid_map:\n",
    "                    for child in pid_map[killed_process[-1]]:\n",
    "                        queue.append(child)\n",
    "            return killed_process\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        n = len(ppid)\n",
    "\n",
    "        pid_map = {}\n",
    "        queue = collections.deque()\n",
    "        root = -1\n",
    "        for p, pp in zip(pid, ppid):\n",
    "            if pp == 0:\n",
    "                root = pp\n",
    "            else:\n",
    "                if pp not in pid_map:\n",
    "                    pid_map[pp] = []\n",
    "                pid_map[pp].append(p)\n",
    "        if kill not in pid_map:\n",
    "            return [kill]\n",
    "        else:\n",
    "            killed_process = []\n",
    "            queue.append(kill)\n",
    "            while queue:\n",
    "                killed_process.append(queue.popleft())\n",
    "                if killed_process[-1] in pid_map:\n",
    "                    for child in pid_map[killed_process[-1]]:\n",
    "                        queue.append(child)\n",
    "            return killed_process"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        max_ = max(pid)\n",
    "        in_degree = [0] * (max_ + 1)\n",
    "        for _ in pid:\n",
    "            in_degree[_] += 1\n",
    "        edges = {}\n",
    "        for pp, p in zip(ppid, pid):\n",
    "            if pp in edges:\n",
    "                edges[pp].append(p)\n",
    "            else:\n",
    "                edges[pp] = [p]\n",
    "\n",
    "        queue = [kill]\n",
    "        results = []\n",
    "        while queue:\n",
    "            curr = queue.pop(0)\n",
    "            results.append(curr)\n",
    "\n",
    "            if curr in edges:\n",
    "                for _ in edges[curr]:\n",
    "                    in_degree[_] -= 1\n",
    "                    if in_degree[_] == 0:\n",
    "                        queue.append(_)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        tree = {}\n",
    "        for i in range(len(pid)):\n",
    "            child = pid[i]\n",
    "            parent = ppid[i]\n",
    "            if parent not in tree:\n",
    "                tree[parent] = []\n",
    "            tree[parent].append(child)\n",
    "\n",
    "        res = []\n",
    "        q = deque([kill])\n",
    "        \n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                cur = q.popleft()\n",
    "                res.append(cur)\n",
    "                if cur in tree:\n",
    "                    q.extend(tree[cur])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        max_ = max(pid)\n",
    "        in_degree = [0] * (max_ + 1)\n",
    "        for _ in pid:\n",
    "            in_degree[_] += 1\n",
    "        edges = {}\n",
    "        for pp, p in zip(ppid, pid):\n",
    "            if pp in edges:\n",
    "                edges[pp].append(p)\n",
    "            else:\n",
    "                edges[pp] = [p]\n",
    "\n",
    "        queue = [kill]\n",
    "        results = []\n",
    "        while queue:\n",
    "            curr = queue.pop(0)\n",
    "            results.append(curr)\n",
    "\n",
    "            if curr in edges:\n",
    "                for _ in edges[curr]:\n",
    "                    in_degree[_] -= 1\n",
    "                    if in_degree[_] == 0:\n",
    "                        queue.append(_)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        removed_process = set()\n",
    "        removed_process.add(kill)\n",
    "        while True:\n",
    "            old_length = len(removed_process)\n",
    "            for i in range(len(ppid)):\n",
    "                if ppid[i] in removed_process:\n",
    "                    removed_process.add(pid[i])\n",
    "            if old_length==len(removed_process):\n",
    "                break\n",
    "        return list(removed_process)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        ans = []\n",
    "        parent = defaultdict(int)\n",
    "        for i in range(len(pid)):\n",
    "            parent[pid[i]]= ppid[i]\n",
    "        \n",
    "        parent[kill] = -1\n",
    "\n",
    "        for i in parent:\n",
    "            r = i\n",
    "            while r !=0 and r!=-1:\n",
    "                r = parent[r]\n",
    "            \n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        parent = defaultdict(int)\n",
    "        n = len(pid)\n",
    "        for i in range(n):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        parent[kill] = -1\n",
    "        ans = []\n",
    "        for i in parent:\n",
    "            r = i \n",
    "            while r != 0 and r != -1:\n",
    "                r = parent[r]\n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        parent = defaultdict(int)\n",
    "        n = len(pid)\n",
    "        # 建立并查集 O(n)\n",
    "        for i in range(n):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        # 设置被杀进程的父节点为 -1\n",
    "        parent[kill] = -1\n",
    "        ans = []\n",
    "        for i in parent:\n",
    "            r = i\n",
    "            # 寻找每个节点的父节点\n",
    "            while r != 0 and r != -1:\n",
    "                r = parent[r]\n",
    "            # 父节点被杀，所以当前节点也被杀了\n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        n = len(pid)\n",
    "        g = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            g[pid[i]] = ppid[i]\n",
    "        \n",
    "        g[kill] = -1\n",
    "        res = []\n",
    "        for i in g:\n",
    "            r = i \n",
    "            while r != 0 and r != -1:\n",
    "                r = g[r]\n",
    "            if r == -1:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        parent = defaultdict(int)\n",
    "        n = len(pid)\n",
    "        # 建立并查集 O(n)\n",
    "        for i in range(n):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        # 设置被杀进程的父节点为 -1\n",
    "        parent[kill] = -1\n",
    "        ans = []\n",
    "        for i in parent:\n",
    "            r = i\n",
    "            # 寻找每个节点的父节点\n",
    "            while r != 0 and r != -1:\n",
    "                r = parent[r]\n",
    "            # 父节点被杀，所以当前节点也被杀了\n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "    #     max_ = max(pid)\n",
    "    #     in_degree = [0] * (max_ + 1)\n",
    "    #     for _ in pid:\n",
    "    #         in_degree[_] += 1\n",
    "    #     edges = {}\n",
    "    #     for pp, p in zip(ppid, pid):\n",
    "    #         if pp in edges:\n",
    "    #             edges[pp].append(p)\n",
    "    #         else:\n",
    "    #             edges[pp] = [p]\n",
    "\n",
    "    #     queue = [kill]\n",
    "    #     results = []\n",
    "    #     while queue:\n",
    "    #         curr = queue.pop(0)\n",
    "    #         results.append(curr)\n",
    "\n",
    "    #         if curr in edges:\n",
    "    #             for _ in edges[curr]:\n",
    "    #                 in_degree[_] -= 1\n",
    "    #                 if in_degree[_] == 0:\n",
    "    #                     queue.append(_)\n",
    "    #     return results\n",
    "\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        parent = defaultdict(int)\n",
    "        n = len(pid)\n",
    "        for i in range(n):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        parent[kill] = -1\n",
    "        ans = []\n",
    "        for i in parent:\n",
    "            r = i\n",
    "            while r != 0 and r != -1:\n",
    "                r = parent[r]\n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        parent = collections.defaultdict(int)\n",
    "        ans = []\n",
    "\n",
    "        for i in range(len(pid)):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        parent[kill] = -1\n",
    "\n",
    "        for i in parent:\n",
    "            q = i\n",
    "            while q != 0 and q != -1:\n",
    "                q = parent[q]\n",
    "            if q == -1:\n",
    "                ans.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        if kill not in ppid: return [kill]\n",
    "\n",
    "        parent = collections.defaultdict(int)\n",
    "\n",
    "        for i in range(len(pid)):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        \n",
    "        parent[kill] = -1\n",
    "        ans = []\n",
    "        for i in parent:\n",
    "            cur = i\n",
    "            while cur != 0 and cur != -1:\n",
    "                cur = parent[cur]\n",
    "            if cur == -1:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "    #     max_ = max(pid)\n",
    "    #     in_degree = [0] * (max_ + 1)\n",
    "    #     for _ in pid:\n",
    "    #         in_degree[_] += 1\n",
    "    #     edges = {}\n",
    "    #     for pp, p in zip(ppid, pid):\n",
    "    #         if pp in edges:\n",
    "    #             edges[pp].append(p)\n",
    "    #         else:\n",
    "    #             edges[pp] = [p]\n",
    "\n",
    "    #     queue = [kill]\n",
    "    #     results = []\n",
    "    #     while queue:\n",
    "    #         curr = queue.pop(0)\n",
    "    #         results.append(curr)\n",
    "\n",
    "    #         if curr in edges:\n",
    "    #             for _ in edges[curr]:\n",
    "    #                 in_degree[_] -= 1\n",
    "    #                 if in_degree[_] == 0:\n",
    "    #                     queue.append(_)\n",
    "    #     return results\n",
    "\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        parent = defaultdict(int)\n",
    "        n = len(pid)\n",
    "        for i in range(n):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        parent[kill] = -1\n",
    "        ans = []\n",
    "        for i in parent:\n",
    "            r = i\n",
    "            while r != 0 and r != -1:\n",
    "                r = parent[r]\n",
    "\n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        parent = defaultdict(int)\n",
    "        n = len(pid)\n",
    "        # 建立并查集 O(n)\n",
    "        for i in range(n):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        # 设置被杀进程的父节点为 -1\n",
    "        parent[kill] = -1\n",
    "        ans = []\n",
    "        for i in parent:\n",
    "            r = i\n",
    "            # 寻找每个节点的父节点\n",
    "            while r != 0 and r != -1:\n",
    "                r = parent[r]\n",
    "            # 父节点被杀，所以当前节点也被杀了\n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in range(len(pid)):\n",
    "            dic[pid[i]] = ppid[i]\n",
    "        dic[kill] = -1\n",
    "        ans = []\n",
    "        for i in dic:\n",
    "            r = i\n",
    "            while r != 0 and r!=-1:\n",
    "                r = dic[r]\n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#并查集就是一棵树。 瞬间我就懂了，并查集实际上是一棵多叉树，用数组来记录每个节点的父节点，初始状态自己是自己的父节点，之后再进行一系列的操作。\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        parent = defaultdict(int)\n",
    "        n = len(pid)\n",
    "        # 建立并查集 ,默认字典(pid[i],ppid[i]),O(n)\n",
    "        for i in range(n):\n",
    "            parent[pid[i]] = ppid[i]\n",
    "        # 设置被杀进程的父节点为-1,kill = 5,parent[5]=-1\n",
    "        parent[kill] = -1\n",
    "        print(parent)\n",
    "        ans = []\n",
    "        for i in parent:#遍历parent并查集{1: 3, 3: 0, 10: 5, 5: -1}  1，3，10，5\n",
    "            r = i\n",
    "            # 寻找每个节点的父节点,每次找父节点时都直到r = 0 或 r = -1停止while循环\n",
    "            while r != 0 and r != -1:\n",
    "                r = parent[r]\n",
    "                print(r)\n",
    "            # 父节点被杀，所以当前节点也被杀了\n",
    "            if r == -1:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        dic={}\n",
    "        for i in range(len(pid)):\n",
    "            if ppid[i] in dic:\n",
    "                dic[ppid[i]].append(pid[i])\n",
    "            else:\n",
    "                dic[ppid[i]]=[pid[i]]\n",
    "\n",
    "        def dfs(index):\n",
    "            if index not in dic:\n",
    "                out.append(index)\n",
    "                return\n",
    "\n",
    "            sons=dic[index]\n",
    "            for son in sons:\n",
    "                dfs(son)\n",
    "            out.append(index)\n",
    "        \n",
    "        out=[]\n",
    "        dfs(kill)\n",
    "        #print(dic)\n",
    "        return out\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        # 每个节点pid只知道自己的父节点ppid, 不知道自己的子节点\n",
    "        # dfs\n",
    "        from collections import defaultdict\n",
    "        n = len(pid)\n",
    "        dct = {}\n",
    "        for i in range(n):  # 构造dfs的图的字典\n",
    "            if ppid[i] not in dct:\n",
    "                dct[ppid[i]] = [pid[i]]\n",
    "            else:\n",
    "                dct[ppid[i]].append(pid[i])\n",
    "        ans = []\n",
    "        def dfs(i):\n",
    "            ans.append(i)\n",
    "            if i not in dct: \n",
    "                return\n",
    "            for j in dct[i]:\n",
    "                dfs(j)\n",
    "            return \n",
    "        dfs(kill)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        if len(ppid) == 0:\n",
    "            return pid\n",
    "        dic = {}\n",
    "        n = len(pid)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if ppid[i] not in dic:\n",
    "                dic[ppid[i]] = [pid[i]]\n",
    "            else:\n",
    "                dic[ppid[i]].append(pid[i])\n",
    "        def dfs(i):\n",
    "            ans.append(i)\n",
    "            if i not in dic:\n",
    "                return\n",
    "            for x in dic[i]:\n",
    "                dfs(x)\n",
    "        dfs(kill)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        # 构建一个字典，将每个父进程对应的所有子进程保存起来\n",
    "        child_processes = {}\n",
    "        # 遍历ppid列表，检查当前父进程是否已经在child_processes中\n",
    "        for i in range(len(ppid)):\n",
    "            if ppid[i] in child_processes:\n",
    "                child_processes[ppid[i]].append(pid[i])\n",
    "            else:\n",
    "                child_processes[ppid[i]] = [pid[i]]\n",
    "        result = []\n",
    "        def dfs(node):\n",
    "            #将当前节点加入结果列表，表示当前进程已经被杀死\n",
    "            result.append(node)\n",
    "            # 递归处理所有子节点\n",
    "            if node in child_processes:\n",
    "                for child in child_processes[node]:\n",
    "                    dfs(child)\n",
    "        # 从给定的pid开始进行深度优先搜索(DFS)\n",
    "        dfs(kill)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in range(len(pid)):\n",
    "            dic[pid[i]] = ppid[i]\n",
    "        killSet, errorSet = set(), set()\n",
    "        killSet.add(kill)\n",
    "        errorSet.add(0)\n",
    "        for p in pid:\n",
    "            tmpSet = set()\n",
    "            while p not in killSet and p not in errorSet:\n",
    "                tmpSet.add(p)\n",
    "                p = dic[p]\n",
    "            if p in killSet:\n",
    "                for i in tmpSet: \n",
    "                    killSet.add(i)\n",
    "            else:\n",
    "                for i in tmpSet: \n",
    "                    errorSet.add(i)\n",
    "        return list(killSet)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.pa = {}\n",
    "        self.size = {}\n",
    "    \n",
    "    def insert(self, x):\n",
    "        self.pa[x] = x\n",
    "        self.size[x] = 1\n",
    "\n",
    "    def find(self, x):\n",
    "        pa = self.pa\n",
    "        if pa[x] == x:\n",
    "            return x\n",
    "        pa[x] = self.find(pa[x])\n",
    "        return pa[x]\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        pa, size = self.pa, self.size\n",
    "        x, y = find(x), find(y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        else:\n",
    "            if size[x] > size[y]:\n",
    "                pa[y] = x\n",
    "                size[x] += size[y]\n",
    "            else:\n",
    "                pa[x] = y\n",
    "                size[y] += size[x]\n",
    "            return 0\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        n = len(pid)\n",
    "        pa = {}\n",
    "        # size = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            c, p = pid[i], ppid[i]\n",
    "            if c == kill:\n",
    "                pa[c] = c\n",
    "                continue\n",
    "            if p not in pa:\n",
    "                pa[p] = p\n",
    "            pa[c] = p\n",
    "            # size[p] += size[c]\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] == x:\n",
    "                return x\n",
    "            pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "\n",
    "        res = []\n",
    "        for c in pid:\n",
    "            if find(c) == kill:\n",
    "                res.append(c)\n",
    "        return res\n",
    "\n",
    "    # def merge(self, x, y):\n",
    "    #     nonlocal size, pa\n",
    "    #     x, y = find(x), find(y)\n",
    "    #     if x == y:\n",
    "    #         return 0\n",
    "    #     else:\n",
    "    #         if size[x] > size[y]:\n",
    "    #             pa[y] = x\n",
    "    #             size[x] += size[y]\n",
    "    #         else:\n",
    "    #             pa[x] = y\n",
    "    #             size[y] += size[x]\n",
    "    #         return 0\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        pid_ppid_map = {}\n",
    "\n",
    "\n",
    "        for pid_, ppid_ in zip(pid, ppid):\n",
    "            pid_ppid_map[pid_] = ppid_\n",
    "        \n",
    "        dq = deque()\n",
    "        dq.append(kill)\n",
    "        visted = set()\n",
    "        visted.add(kill)\n",
    "\n",
    "        ret = []\n",
    "        while dq:\n",
    "            killed = dq.popleft()\n",
    "            ret.append(killed)\n",
    "\n",
    "            to_kill = []\n",
    "            for pid in pid_ppid_map:\n",
    "                if pid_ppid_map[pid] == killed:\n",
    "                    to_kill.append(pid)\n",
    "            \n",
    "            for pid in to_kill:\n",
    "                dq.append(pid)\n",
    "                visted.add(pid)\n",
    "                del pid_ppid_map[pid]\n",
    "        \n",
    "        return ret\n",
    "                     \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        sondt=dict()\n",
    "        for i in range(len(ppid)):\n",
    "            if ppid[i] in sondt:\n",
    "                sondt[ppid[i]].append(pid[i])\n",
    "            else:\n",
    "                sondt[ppid[i]]=[pid[i]]\n",
    "        def killee(i):\n",
    "            nonlocal ans\n",
    "            ans.append(i)\n",
    "            if i in sondt:\n",
    "                for j in sondt[i]:\n",
    "                    killee(j)\n",
    "            else:\n",
    "                return \n",
    "        ans=[]\n",
    "        killee(kill)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.pa = {}\n",
    "        self.size = {}\n",
    "    \n",
    "    def insert(self, x):\n",
    "        self.pa[x] = x\n",
    "        self.size[x] = 1\n",
    "\n",
    "    def find(self, x):\n",
    "        pa = self.pa\n",
    "        if pa[x] == x:\n",
    "            return x\n",
    "        pa[x] = self.find(pa[x])\n",
    "        return pa[x]\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        pa, size = self.pa, self.size\n",
    "        x, y = find(x), find(y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        else:\n",
    "            if size[x] > size[y]:\n",
    "                pa[y] = x\n",
    "                size[x] += size[y]\n",
    "            else:\n",
    "                pa[x] = y\n",
    "                size[y] += size[x]\n",
    "            return 0\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        n = len(pid)\n",
    "        pa = {}\n",
    "        size = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            c, p = pid[i], ppid[i]\n",
    "            if c == kill:\n",
    "                pa[c] = c\n",
    "                continue\n",
    "            if p not in pa:\n",
    "                pa[p] = p\n",
    "            pa[c] = p\n",
    "            size[p] += size[c]\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] == x:\n",
    "                return x\n",
    "            pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "\n",
    "        res = []\n",
    "        for c in pid:\n",
    "            if find(c) == kill:\n",
    "                res.append(c)\n",
    "        return res\n",
    "\n",
    "    # def merge(self, x, y):\n",
    "    #     nonlocal size, pa\n",
    "    #     x, y = find(x), find(y)\n",
    "    #     if x == y:\n",
    "    #         return 0\n",
    "    #     else:\n",
    "    #         if size[x] > size[y]:\n",
    "    #             pa[y] = x\n",
    "    #             size[x] += size[y]\n",
    "    #         else:\n",
    "    #             pa[x] = y\n",
    "    #             size[y] += size[x]\n",
    "    #         return 0\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.pa = {}\n",
    "        self.size = {}\n",
    "    \n",
    "    def insert(self, x):\n",
    "        self.pa[x] = x\n",
    "        self.size[x] = 1\n",
    "\n",
    "    def find(self, x):\n",
    "        pa = self.pa\n",
    "        if pa[x] == x:\n",
    "            return x\n",
    "        pa[x] = self.find(pa[x])\n",
    "        return pa[x]\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        pa, size = self.pa, self.size\n",
    "        x, y = find(x), find(y)\n",
    "        if x == y:\n",
    "            return 0\n",
    "        else:\n",
    "            if size[x] > size[y]:\n",
    "                pa[y] = x\n",
    "                size[x] += size[y]\n",
    "            else:\n",
    "                pa[x] = y\n",
    "                size[y] += size[x]\n",
    "            return 0\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        n = len(pid)\n",
    "        pa = {}\n",
    "        size = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            c, p = pid[i], ppid[i]\n",
    "            if c == kill:\n",
    "                pa[c] = c\n",
    "                continue\n",
    "            if p not in pa:\n",
    "                pa[p] = p\n",
    "            pa[c] = p\n",
    "            size[p] += size[c]\n",
    "\n",
    "        def find(x):\n",
    "            if pa[x] == x:\n",
    "                return x\n",
    "            pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "\n",
    "        res = []\n",
    "        for c in pid:\n",
    "            if find(c) == kill:\n",
    "                res.append(c)\n",
    "        return res\n",
    "\n",
    "    # def merge(self, x, y):\n",
    "    #     nonlocal size, pa\n",
    "    #     x, y = find(x), find(y)\n",
    "    #     if x == y:\n",
    "    #         return 0\n",
    "    #     else:\n",
    "    #         if size[x] > size[y]:\n",
    "    #             pa[y] = x\n",
    "    #             size[x] += size[y]\n",
    "    #         else:\n",
    "    #             pa[x] = y\n",
    "    #             size[y] += size[x]\n",
    "    #         return 0\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        # todo: some input check\n",
    "\n",
    "        from collections import defaultdict \n",
    "\n",
    "        mapping = defaultdict(list)\n",
    "        for i in range(len(pid)):\n",
    "            process = pid[i]\n",
    "            parent = ppid[i]\n",
    "            mapping[parent].append(process)\n",
    "        \n",
    "        res = []\n",
    "        self._dfs(kill, mapping, res)   \n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "    def _dfs(self, node, mapping, res):\n",
    "        res.append(node)\n",
    "        \n",
    "        if not mapping[node]:\n",
    "            return \n",
    "    \n",
    "        for n in mapping[node]:\n",
    "            self._dfs(n, mapping, res)\n",
    "        \n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        hashmap = defaultdict(list)\n",
    "\n",
    "        for i in range(len(pid)):\n",
    "            child = pid[i]\n",
    "            pat = ppid[i]\n",
    "\n",
    "            hashmap[pat].append(child)\n",
    "\n",
    "        q = [kill]\n",
    "        res = []\n",
    "\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            res.append(cur)\n",
    "            for child in hashmap[cur]:\n",
    "                q.append(child)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        e=collections.defaultdict(list)\n",
    "        for i in range(len(pid)):\n",
    "            now,fa=pid[i],ppid[i]\n",
    "            e[fa].append(now)\n",
    "        q=collections.deque()\n",
    "        q.append(kill)\n",
    "        ret=[]\n",
    "        while q:\n",
    "            tp=q.popleft()\n",
    "            ret.append(tp)\n",
    "            for i in e[tp]:\n",
    "                q.append(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        ans = []\n",
    "        killed_ = [kill]\n",
    "        kid = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            kid[ppid[i]].append(pid[i])\n",
    "        print(kid)\n",
    "\n",
    "        while killed_:\n",
    "            i = killed_.pop()\n",
    "            ans.append(i)\n",
    "            for j in kid[i]:\n",
    "                killed_.append((j))\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        d = defaultdict(list)\n",
    "        for i in range(len(pid)):\n",
    "            d[ppid[i]].append(pid[i])\n",
    "\n",
    "        ans = []\n",
    "        queue = deque([kill])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            ans.append(cur)\n",
    "            for next in d[cur]:\n",
    "                queue.append(next)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            p = ppid[i]\n",
    "            graph[p].append(pid[i])\n",
    "        q = deque()\n",
    "        q.append(kill)\n",
    "        ans = []\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            ans.append(p)\n",
    "            for n in graph[p]:\n",
    "                q.append(n)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        ans = []\n",
    "        killed_ = [kill]\n",
    "        kid = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            kid[ppid[i]].append(pid[i])\n",
    "        print(kid)\n",
    "\n",
    "        while killed_:\n",
    "            i = killed_.pop()\n",
    "            ans.append(i)\n",
    "            for j in kid[i]:\n",
    "                killed_.append((j))\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        ad=collections.defaultdict(list)\n",
    "\n",
    "        for i,fa in enumerate(ppid):\n",
    "            if fa==0:\n",
    "                continue\n",
    "            son=pid[i]\n",
    "            ad[fa].append(son)\n",
    "        stack=collections.deque()\n",
    "        stack.append(kill)\n",
    "        ans=[]\n",
    "        while stack:\n",
    "            cur =stack.popleft()\n",
    "            ans.append(cur)\n",
    "            for nex in ad[cur]:\n",
    "                stack.append(nex)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        d = defaultdict(list)\n",
    "        for p,pp in zip(pid,ppid):\n",
    "            if pp==0: continue\n",
    "            d[pp].append(p)\n",
    "        res = []\n",
    "        q = deque([kill])\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            res.append(p)\n",
    "            for c in d[p]:\n",
    "                q.append(c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        ans = []\n",
    "        jobs = collections.deque()\n",
    "        jobs.append(kill)\n",
    "        parent = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            parent[ppid[i]].append(pid[i])\n",
    "\n",
    "\n",
    "\n",
    "        while len(jobs) >0:\n",
    "            job = jobs.popleft()\n",
    "            ans.append(job)\n",
    "\n",
    "            for c in parent[job]:\n",
    "                jobs.append(c)\n",
    "\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        \n",
    "        plist = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            plist[ppid[i]].append(pid[i])\n",
    "\n",
    "        res = []\n",
    "        stack = [kill]\n",
    "        \n",
    "        while(stack):\n",
    "            curid = stack.pop(0)\n",
    "            res.append(curid)\n",
    "            for i in plist[curid]:\n",
    "                stack.append(i)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        record = collections.defaultdict(list)\n",
    "        for i in range(len(pid)):\n",
    "            record[ppid[i]].append(pid[i])\n",
    "        \n",
    "        res = []\n",
    "        queue = [kill]\n",
    "        while queue:\n",
    "            proc = queue.pop(0)\n",
    "            res.append(proc)\n",
    "            for node in record[proc]:\n",
    "                queue.append(node)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        res=[]\n",
    "        queue=collections.deque()\n",
    "        queue.append(kill)\n",
    "        hashmap=collections.defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            hashmap[ppid[i]].append(pid[i])\n",
    "        while(len(queue)>0):\n",
    "            father=queue.popleft()\n",
    "            res.append(father)\n",
    "            queue+=hashmap[father]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        \n",
    "        plist = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            plist[ppid[i]].append(pid[i])\n",
    "\n",
    "        res = []\n",
    "        stack = [kill]\n",
    "        \n",
    "        while(stack):\n",
    "            curid = stack.pop(0)\n",
    "            res.append(curid)\n",
    "            for i in plist[curid]:\n",
    "                stack.append(i)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x,y in zip(pid,ppid):\n",
    "            g[y].append(x)\n",
    "        \n",
    "        ans = []\n",
    "        # def dfs(node_id):\n",
    "        #     ans.append(node_id)\n",
    "        #     for x in g[node_id]:\n",
    "        #         dfs(x)\n",
    "        # dfs(kill)\n",
    "\n",
    "        stack = [kill]\n",
    "        while stack:\n",
    "            x = stack.pop()\n",
    "            ans.append(x)\n",
    "            for nx in g[x]:\n",
    "                stack.append(nx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        n = len(pid)\n",
    "        g = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            g[ppid[i]].append(pid[i])\n",
    "        \n",
    "        res = []\n",
    "        st = [kill]\n",
    "        while st:\n",
    "            res.extend(st)\n",
    "            nxt = []\n",
    "            for i in st:\n",
    "                for j in g[i]:\n",
    "                    nxt.append(j)\n",
    "            st = nxt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        \n",
    "        plist = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            plist[ppid[i]].append(pid[i])\n",
    "\n",
    "        res = []\n",
    "        stack = [kill]\n",
    "        \n",
    "        while(stack):\n",
    "            curid = stack.pop(0)\n",
    "            res.append(curid)\n",
    "            for i in plist[curid]:\n",
    "                stack.append(i)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        record = collections.defaultdict(list)\n",
    "        for i in range(len(pid)):\n",
    "            record[ppid[i]].append(pid[i])\n",
    "        \n",
    "        res = []\n",
    "        queue = [kill]\n",
    "        visited = set()\n",
    "        while queue:\n",
    "            proc = queue.pop(0)\n",
    "            res.append(proc)\n",
    "            for node in record[proc]:\n",
    "                if node not in visited:\n",
    "                    queue.append(node)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        children = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(pid)):\n",
    "            p = pid[i]\n",
    "            pp = ppid[i]\n",
    "            children[pp].append(p)\n",
    "\n",
    "        todo = [kill]\n",
    "        ret = [kill]\n",
    "        while todo:\n",
    "            tmp = []\n",
    "            for c in todo:\n",
    "                tmp.extend(children[c])\n",
    "            ret.extend(tmp)\n",
    "            todo = tmp\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "#         # res=[]\n",
    "#         # if kill==0:\n",
    "#         #     return []\n",
    "        \n",
    "#         # res.append(kill)\n",
    "\n",
    "#         # for i in range(len(ppid)):\n",
    "#         #     if ppid.getindex(i)==kull:\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "#         parent = defaultdict(int)\n",
    "#         n = len(pid)\n",
    "#         # 建立并查集 O(n)\n",
    "#         for i in range(n):\n",
    "#             parent[pid[i]] = ppid[i]\n",
    "#         # 设置被杀进程的父节点为 -1\n",
    "#         parent[kill] = -1\n",
    "#     #   print(parent)\n",
    "#         ans = []\n",
    "#         for i in parent:\n",
    "#             r = i\n",
    "#             # 寻找每个节点的父节点\n",
    "#             while r != 0 and r != -1:\n",
    "#                 # print(parent[r])\n",
    "#                 r = parent[r]\n",
    "#             # 父节点被杀，所以当前节点也被杀了\n",
    "#             if r == -1:\n",
    "#                 ans.append(i)\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        # if \n",
    "\n",
    "\n",
    "        n=len(pid)\n",
    "        dct=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dct[ppid[i]].append(pid[i])\n",
    "        \n",
    "        res=[]\n",
    "        stack=[kill]\n",
    "        while stack:\n",
    "            res.extend(stack)\n",
    "            next_=[]\n",
    "            for i in stack:\n",
    "                # for j in dct[i]:\n",
    "                next_.extend(dct[i])\n",
    "            \n",
    "            stack=next_\n",
    "\n",
    "        return res\n",
    "\n",
    "        # # print(dct)\n",
    "        # res=[]\n",
    "        # def dfs(kill):\n",
    "        #     res.append(kill)\n",
    "        #     for i in dct[kill]:\n",
    "        #         dfs(i)\n",
    "            \n",
    "        #     return\n",
    "        # dfs(kill)\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "\n",
    "        n = len(pid)\n",
    "        dct = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dct[ppid[i]].append(pid[i])\n",
    "            \n",
    "        ans = []\n",
    "        stack = [kill]\n",
    "        while stack:\n",
    "            ans.extend(stack)\n",
    "            nex = []\n",
    "            for i in stack:\n",
    "                for j in dct[i]:\n",
    "                    nex.append(j)\n",
    "            stack = nex\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "      from collections import defaultdict\n",
    "\n",
    "      father2sons = defaultdict(list)\n",
    "      for f,s in zip(ppid,pid):\n",
    "        father2sons[f].append(s)\n",
    "\n",
    "      goon = True\n",
    "      res = [kill]\n",
    "      just_killed = [kill]\n",
    "      while goon:\n",
    "        new_kill = []\n",
    "        for x in just_killed:\n",
    "          res+=father2sons[x]\n",
    "          new_kill+=father2sons[x]\n",
    "        goon = len(new_kill)>0\n",
    "        just_killed = new_kill\n",
    "      return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        d = collections.defaultdict(list)\n",
    "        for p, pp in zip(pid, ppid):\n",
    "            d[pp].append(p)\n",
    "\n",
    "        ret = [kill]\n",
    "        l = [kill]\n",
    "        while l:\n",
    "            for child in d[l.pop()]:\n",
    "                ret.append(child)\n",
    "                l.append(child)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        ans = [kill]\n",
    "        killed_ = [kill]\n",
    "        kid = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            kid[ppid[i]].append(pid[i])\n",
    "        print(kid)\n",
    "\n",
    "        while killed_:\n",
    "            i = killed_.pop()\n",
    "            for j in kid[i]:\n",
    "                ans.append(j)\n",
    "                killed_.append((j))\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x, p in zip(pid, ppid):\n",
    "            g[p].append(x)\n",
    "        dq = deque([(0, False)])\n",
    "        ans = []\n",
    "        while dq:\n",
    "            x, flag = dq.popleft()\n",
    "            if flag: ans.append(x)\n",
    "            for y in g[x]:\n",
    "                dq.append((y, flag or y == kill))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        ans = [kill]\n",
    "        killed_ = [kill]\n",
    "        kid = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            kid[ppid[i]].append(pid[i])\n",
    "        print(kid)\n",
    "\n",
    "        while killed_:\n",
    "            i = killed_.pop()\n",
    "            for j in kid[i]:\n",
    "                ans.append(j)\n",
    "                killed_.append((j))\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        ans = [kill]\n",
    "        killed_ = [kill]\n",
    "        kid = defaultdict(list)\n",
    "        for i in range(len(ppid)):\n",
    "            kid[ppid[i]].append(pid[i])\n",
    "        print(kid)\n",
    "\n",
    "        while killed_:\n",
    "            i = killed_.pop()\n",
    "            for j in kid[i]:\n",
    "                ans.append(j)\n",
    "                killed_.append((j))\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        tree = collections.defaultdict(list)\n",
    "        for index in range(len(pid)):\n",
    "            child, parent = pid[index], ppid[index]\n",
    "            tree[parent].append(child)\n",
    "        \n",
    "        def killNode(node, result):\n",
    "            result += [node]\n",
    "            for child in tree[node]:\n",
    "                killNode(child, result)\n",
    "            return result\n",
    "\n",
    "        return killNode(kill, [])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        result, d = [kill], defaultdict(list)\n",
    "        for n, p in zip(pid, ppid):\n",
    "            d[p].append(n)\n",
    "        dfs = lambda i: any(result.append(j) or dfs(j) for j in d[i])\n",
    "        return dfs(kill) or result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        maps = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(len(pid)):\n",
    "            maps[ppid[i]].append(pid[i])\n",
    "        \n",
    "        def dfs(x):\n",
    "            if x in maps[x]:\n",
    "                return maps[x]\n",
    "            path = [x]\n",
    "            for i in maps[x]:\n",
    "                path.extend(dfs(i))\n",
    "            return path\n",
    "        return dfs(kill)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        return self.answer_2(pid, ppid, kill)\n",
    "    def answer_2(self, pids, ppids, kill):\n",
    "        ppid_mapper = collections.defaultdict(list)\n",
    "\n",
    "        for index, ppid in enumerate(ppids):\n",
    "            ppid_mapper[ppid].append(pids[index])\n",
    "\n",
    "        result = []\n",
    "\n",
    "        def _dfs(i):\n",
    "            result.append(i)\n",
    "\n",
    "            for j in ppid_mapper[i]:\n",
    "                _dfs(j)\n",
    "\n",
    "        _dfs(kill)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        childs = defaultdict(list)\n",
    "\n",
    "        n = len(pid)\n",
    "\n",
    "        for i in range(n):\n",
    "            childs[ppid[i]].append(pid[i])\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        def dfs(index: int) -> None:\n",
    "            ans.append(index)\n",
    "            for child in childs[index]:\n",
    "                dfs(child)\n",
    "\n",
    "        dfs(kill)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for x,y in zip(pid,ppid):\n",
    "            g[y].append(x)\n",
    "        \n",
    "        ans = []\n",
    "        def dfs(node_id):\n",
    "            ans.append(node_id)\n",
    "            for x in g[node_id]:\n",
    "                dfs(x)\n",
    "        \n",
    "        dfs(kill)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        dict = defaultdict(list)\n",
    "        for i in range(len(pid)):\n",
    "            dict[ppid[i]].append(pid[i])\n",
    "        \n",
    "        def dfs(x):\n",
    "            res.append(x)\n",
    "            for i in dict[x]:\n",
    "                dfs(i)\n",
    "            return\n",
    "       \n",
    "        res = []\n",
    "        dfs(kill)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        childs = defaultdict(list)\n",
    "        n = len(pid)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            childs[ppid[i]].append(pid[i])\n",
    "        def dfs(i):\n",
    "            res.append(i)\n",
    "            for child in childs[i]:\n",
    "                dfs(child)\n",
    "        dfs(kill)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "#         # res=[]\n",
    "#         # if kill==0:\n",
    "#         #     return []\n",
    "        \n",
    "#         # res.append(kill)\n",
    "\n",
    "#         # for i in range(len(ppid)):\n",
    "#         #     if ppid.getindex(i)==kull:\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "#         parent = defaultdict(int)\n",
    "#         n = len(pid)\n",
    "#         # 建立并查集 O(n)\n",
    "#         for i in range(n):\n",
    "#             parent[pid[i]] = ppid[i]\n",
    "#         # 设置被杀进程的父节点为 -1\n",
    "#         parent[kill] = -1\n",
    "#     #   print(parent)\n",
    "#         ans = []\n",
    "#         for i in parent:\n",
    "#             r = i\n",
    "#             # 寻找每个节点的父节点\n",
    "#             while r != 0 and r != -1:\n",
    "#                 # print(parent[r])\n",
    "#                 r = parent[r]\n",
    "#             # 父节点被杀，所以当前节点也被杀了\n",
    "#             if r == -1:\n",
    "#                 ans.append(i)\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        n=len(pid)\n",
    "        dct=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dct[ppid[i]].append(pid[i])\n",
    "\n",
    "        # print(dct)\n",
    "        res=[]\n",
    "        def dfs(kill):\n",
    "            res.append(kill)\n",
    "            for i in dct[kill]:\n",
    "                dfs(i)\n",
    "            \n",
    "            return\n",
    "        dfs(kill)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        def dfs(i: int):\n",
    "            ans.append(i)\n",
    "            for j in g[i]:\n",
    "                dfs(j)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for i, p in zip(pid, ppid):\n",
    "            g[p].append(i)\n",
    "        ans = []\n",
    "        dfs(kill)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        childrenDict = defaultdict(list)\n",
    "        for i in range(0, len(pid)):\n",
    "            if ppid[i] not in childrenDict: \n",
    "                childrenDict[ppid[i]] = [pid[i]]\n",
    "            else:  \n",
    "                childrenDict[ppid[i]].append(pid[i]) \n",
    "        def dfs(i): \n",
    "            ans.append(i) \n",
    "            for j in childrenDict[i]:\n",
    "                dfs(j) \n",
    "            return \n",
    "        ans = [] \n",
    "        dfs(kill) \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        myDict = defaultdict(list)\n",
    "        needKill = set()\n",
    "        needKill.add(kill)\n",
    "        n = len(ppid)\n",
    "        for i in range(n):\n",
    "            myDict[ppid[i]].append(pid[i])\n",
    "        myKill = [kill]\n",
    "        while myKill:\n",
    "            curKill = myKill.pop(0)\n",
    "            for ele in myDict[curKill]:\n",
    "                myKill.append(ele)\n",
    "                needKill.add(ele)\n",
    "        # print(needKill)\n",
    "        return list(needKill)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        myDict = defaultdict(list)\n",
    "        needKill = set()\n",
    "        needKill.add(kill)\n",
    "        n = len(ppid)\n",
    "        for i in range(n):\n",
    "            myDict[ppid[i]].append(pid[i])\n",
    "        myKill = [kill]\n",
    "        while myKill:\n",
    "            curKill = myKill.pop(0)\n",
    "            for ele in myDict[curKill]:\n",
    "                myKill.append(ele)\n",
    "                needKill.add(ele)\n",
    "        print(needKill)\n",
    "        return list(needKill)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        pid_ppid_map = defaultdict(list)\n",
    "\n",
    "        all_ids = set()\n",
    "\n",
    "        for pid_, ppid_ in zip(pid, ppid):\n",
    "            pid_ppid_map[ppid_].append(pid_)\n",
    "            all_ids.add(pid_)\n",
    "            all_ids.add(ppid_)\n",
    "\n",
    "        dq = deque()\n",
    "        dq.append(kill)\n",
    "        \n",
    "        ret = []\n",
    "        while dq:\n",
    "            killed = dq.popleft()\n",
    "            ret.append(killed)\n",
    "            all_ids.remove(killed)\n",
    "\n",
    "            for pid in pid_ppid_map[killed]:\n",
    "                if pid in all_ids:\n",
    "                    dq.append(pid)\n",
    "            \n",
    "        return ret\n",
    "                     \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        pid_ppid_map = defaultdict(list)\n",
    "\n",
    "        all_ids = set()\n",
    "\n",
    "        for pid_, ppid_ in zip(pid, ppid):\n",
    "            pid_ppid_map[ppid_].append(pid_)\n",
    "            all_ids.add(pid_)\n",
    "            all_ids.add(ppid_)\n",
    "\n",
    "        dq = deque()\n",
    "        dq.append(kill)\n",
    "        visted = set()\n",
    "        visted.add(kill)\n",
    "        \n",
    "        ret = []\n",
    "        while dq:\n",
    "            killed = dq.popleft()\n",
    "            ret.append(killed)\n",
    "            all_ids.remove(killed)\n",
    "\n",
    "            for pid in pid_ppid_map[killed]:\n",
    "                if pid in all_ids:\n",
    "                    dq.append(pid)\n",
    "            \n",
    "        return ret\n",
    "                     \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "class Solution:\n",
    "    def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:\n",
    "        pidchildpi = defaultdict(list)\n",
    "        for ppi, ppid in enumerate(ppid):\n",
    "            pidchildpi[ppid].append(ppi)\n",
    "\n",
    "        travq = deque()\n",
    "        travq.append(kill)\n",
    "        visited = set()\n",
    "        while len(travq):\n",
    "            cpid = travq.popleft()\n",
    "            if cpid in visited:\n",
    "                continue\n",
    "            travq.extend([pid[childpi] for childpi in pidchildpi[cpid]])\n",
    "            visited.add(cpid)\n",
    "        return list(visited)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
